package com.fw.leetcode.linkedlist;

import com.fw.leetcode.LeetCode;

/**
 * 143. Reorder List
 *
 * You are given the head of a singly linked-list. The list can be represented as:
 *   L0 → L1 → … → Ln - 1 → Ln
 * Reorder the list to be on the following form:
 *   L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …
 * You may not modify the values in the list's nodes. Only nodes themselves may be changed.
 *
 * Example 1:
 *  Input: head = [1,2,3,4]
 *  Output: [1,4,2,3]
 *
 * Example 2:
 *  Input: head = [1,2,3,4,5]
 *  Output: [1,5,2,4,3]
 *
 * Constraints:
 *  The number of nodes in the list is in the range [1, 5 * 10^4].
 *  1 <= Node.val <= 1000
 */
public class Num_0143 implements LeetCode {
    private interface Solution extends LinkedList {
        void reorderList(ListNode head);

        default void assertExpected(int[] head, int[] expected) {
            ListNode headNode = build(head);
            reorderList(headNode);
            if (!assertEquals(headNode, build(expected))) {
                reorderList(build(head));
            }
        }
    }

    private static class MyFastSlowPointerSolution implements Solution {

        private ListNode middleNode(ListNode head) {
            ListNode fast = head;
            ListNode slow = head;
            while (fast != null && fast.next != null) {
                fast = fast.next.next; // fast 进两步
                slow = slow.next; // slow 进一步
            }
            return slow;
        }

        private ListNode reverseNode(ListNode head) {
            ListNode reverseHead = null;
            ListNode cur = head;
            ListNode curNext;
            while (cur != null) {
                curNext = cur.next;
                // 插入头
                cur.next = reverseHead;
                reverseHead = cur;
                // 后移
                cur = curNext;
            }
            return reverseHead;
        }

        @Override
        public void reorderList(ListNode head) { // 最优：快慢指针寻中点切割+反转链表+交叉合并：时O(n) 空O(1)
            /*
             * 重排链表
             * 共需移动元素个数：(n-1)/2 即中点（可用快慢指针），将待移动元素进行倒排，再交叉合并
             *     head-> [1,2,3,| 4,5]  <- 即中点 3 处
             * 1:  head-> [1,5,2,3,4]
             * 2:  head-> [1,5,2,4,3]
             *
             *     head-> [1,2,3,4,| 5,6]  <- 即中点 4 处（两个中点取后一个）
             * 1:  head-> [1,6,2,3,4,5]
             * 2:  head-> [1,6,2,5,3,4]
             */
            // 1.快慢指针寻找中点
            ListNode middle = middleNode(head);
            // 2.反转中点后半部分链表
            ListNode reverseHeader = new ListNode(-1, reverseNode(middle.next)); // 建立辅助头节点
            middle.next = null; // 切断后半部分
            // 3.交叉合并
            ListNode header = new ListNode(-1, head); // 建立辅助头节点
            ListNode cur = header.next;
            while (cur != null) { // 逐个插入 cur 之后
                if (reverseHeader.next == null) {
                    break;
                }
                // moveHeader 头出队
                ListNode insertNode = reverseHeader.next;
                reverseHeader.next = insertNode.next;
                // 插入 header cur 之后
                insertNode.next = cur.next;
                cur.next = insertNode;
                // cur 越过插入元素，指向后一个
                cur = insertNode.next;
            }
        }
    }

    private static class MySolution implements Solution {

        @Override
        public void reorderList(ListNode head) { // 其次：中点切割+倒排+交叉合并：时O(n) 空O(1)
            /*
             * 重排链表，有点难度
             * 共需移动元素个数：(n-1)/2，将待移动元素进行倒排，再交叉合并
             *     head-> [1,2,3,4,5]
             *
             * 1:  head-> [1,5,2,3,4]
             * 2:  head-> [1,5,2,4,3]
             *
             * 切割出后半部分需要移动的元素，进行倒排
             *            [5 | -> 6 -> 7 -> 8 -> 9]
             *             ↑      ↑    ↑
             * 1:         [5 <- 6 | -> 7 -> 8 -> 9]
             *                  ↑      ↑    ↑
             * 2:         [5 <- 6 <- 7 | -> 8 -> 9]
             *                       ↑      ↑    ↑
             * 3:         [5 <- 6 <- 7 <- 8 | -> 9]  null
             *                            ↑      ↑   ↑
             * 4:         [5 <- 6 <- 7 <- 8 <- 9] <- head
             *                                 ↑      ↑
             */
            ListNode header = new ListNode(-1, head); // 建立辅助头节点
            ListNode cur = header.next;
            int n = 1;
            // 1.遍历计算节点总数
            while (cur.next != null) {
                n++;
                cur = cur.next;
            }
            if (n < 3) { // 1|2 个不需移动
                return;
            }
            int num = (n-1) / 2; // 共需移动个数
            // 2. 后半部分移动元素倒排成单独链表
            cur = header.next;
            for (int i = 0; i < n - num - 1; i++) {
                cur = cur.next;
            }
            ListNode first = cur.next; // 起点
            cur.next = null; // 前后切断
            ListNode second = first.next;
            first.next = null; // 头即是尾，置空next
            ListNode third;
            while (second != null) {
                // 转向
                third = second.next;
                second.next = first;
                // 后移
                first = second;
                second = third;
            }
            ListNode moveHeader = new ListNode(-1, first);
            // 3.交叉合并
            cur = header.next;
            while (cur != null) { // 逐个插入 cur 之后
                if (moveHeader.next == null) {
                    break;
                }
                // moveHeader 头出队
                ListNode insertNode = moveHeader.next;
                moveHeader.next = insertNode.next;
                // 插入 header cur 之后
                insertNode.next = cur.next;
                cur.next = insertNode;
                // cur 越过插入元素，指向后一个
                cur = insertNode.next;
            }
        }
    }

    public static void main(String[] args) {
        Solution solution = new MyFastSlowPointerSolution();
        solution.assertExpected(new int[]{1}, new int[]{1});
        solution.assertExpected(new int[]{1,2}, new int[]{1,2});
        solution.assertExpected(new int[]{1,2,3}, new int[]{1,3,2});
        solution.assertExpected(new int[]{1,2,3,4}, new int[]{1,4,2,3});
        solution.assertExpected(new int[]{1,2,3,4,5}, new int[]{1,5,2,4,3});
    }
}
